Discrete Mathematics for Computer Science/Proof

Type classification: this is a lesson resource.

A proof is a sequence of logical deductions, based on accepted assumptions and previously proven statements and verifying that a statement is true. What constitutes a proof may vary, depending on the field.

In mathematics, a formal proof of a proposition is a chain of logical deductions leading to the proposition from a base set of axioms. We'll be discussing propositions, logical deductions and axioms.

Propositions

• Definition: A statement that is either true or false.

Which statement is a proposition?

Which bird did the cat kill? WRONG! Try again.

William's wife's name is Irene. Correct!

Wherefore art thou, Romeo? WRONG! Try again.

Give me an A! WRONG! Try again.

Which statement is not a proposition?

Roland's daughter is Rolanda. WRONG! Try again.

His tomb says "Trail Blazer." WRONG! Try again.

Roland won many awards. WRONG! Try again.

Tell me what Roland does. Correct!

Which statement is a proposition?

A. 2 + 3 = 5 Read the question again!

B. 4 / 9 WRONG! Try again.

C. 1 + 1 = 3 Read the question again!

D. Both A and C Correct!

Propositions: True or false?

One must be cautious in assuming that propositions which apply to an infinite set of elements can be checked using a finite subset. For example:

• a⁴ + b⁴ + c⁴ = d⁴ has no solution when a, b, c and d are positive integers.
  • This equation was proven false with values of a, b, c and d in the tens and hundreds of thousands.
• The four-color theorem: Every map can be colored with four colors so that no two adjacent countries are assigned the same color.
  • This theorem is true, but many incorrect proofs were accepted for long periods of time. (This theorem can be false, though, if a country is not contiguous (it has exclaves) but must all be colored uniformly, but this is a complicated case.)
• The Goldbach Conjecture: Every even integer greater than 2 is the sum of two primes.
  • No one knows if this conjecture is true or false!

The Axiomatic Method

• The axiomatic method is the method of forming proofs based on axioms and previously-proven statements.
  • Axiom: a proposition that is simply accepted as true.
  • Euclid pioneered the axiomatic method in his geometric proofs. Euclid's proofs were based on five fundamental axioms, such as the axiom that one and only straight line segment can be drawn between each pair of points. See this page for a more specifically geometric concept of proofs.
  • Euclid's axiomatic method has become the foundation of modern mathematics! Today, the ZFC axioms are the handful of axioms from which modern mathematics is derived.

• There are several common terms for a proposition which has been proven true:
  • Theorem: A particularly important proposition.
  • Lemma: A preliminary proposition useful for proving later propositions.
  • Corollary: An afterthought, a proposition that follows in just a few short steps from a theorem.

• And again, the general term for proof (which you now understand somewhat better):
  • A sequence of logical deductions from axioms and previously-proven statements, which concludes with the proposition in question.

Proving an Implication

Many claims in mathematics are formulated as: "P implies Q." These are called implications. This section will teach you the format of writing a proof, and walk you through some example proofs. There are a few standard methods for proving an implication, and a couple of points that apply to all proofs.

• You'll often need to do some scratchwork while you're trying to figure out the logical steps of a proof. Your scratchwork can be as disorganized as you like--full of dead ends, strange diagrams, obscene words, whatever. But keep your scratchwork separate from your final proof, which should be clear and concise.
• Proofs typically begin with the word "Proof," and end with some sort of indication like Q.E.D. This clarifies when the proofs begin and end.

Now we will go over some of the basic methods of proving an implication.

1. Write: "Assume P." Show that Q logically follows.

• Example: Prove that if 0 ≤ x ≤ 2, then -x³ + 4x + 1 > 0.
• Solution: Before we write a proof of this theorem, we need to do some scratchwork to figure out why it is true. The inequality certainly holds for x = 0; there, the left side is equal to 1 and 1 > 0. As x grows, the 4x term (which is positive) initially seems to have greater magnitude than -x³ (which is negative). For example, when x = 1, we have 4x = 4, but -x³ = -1 only. In fact, it looks like -x³ doesn't begin to dominate until x > 2. So it seems the -x³ + 4x part should be nonnegative for all x between 0 and 2, which would imply that -x³ + 4x + 1 is positive.

So far, so good. But we still have to replace all those "seems like" phrases with solid, logical arguments. We can get a better handle on the -x³ + 4x part by factoring it, without too much difficulty, into x(2 - x)(2 + x).

Aha! For x between 0 and 2, all terms on the right side are nonnegative. And a product of nonnegative terms is also nonnegative. We can organize these observations into a clean proof.

• Proof: Assume 0 ≤ x ≤ 2. Then x, 2 - x and 2 + x are all nonnegative. Therefore, the product of these terms is also nonnegative. Adding 1 to this product gives a positive number, so:

x(2 - x)(2 + x) + 1 > 0

Multiplying on the left side proves that:

-x³ + 4x + 1 > 0

as claimed.

2. Prove the contrapositive.

• An implication "P implies Q" is logically equivalent to its contrapositive, "~Q implies ~P." Often, proving the contrapositive is easier than proving the original statement. In order to prove the contrapositive, one must write "We prove the contrapositive," state the contrapositive, and then proceed.

• Example: Prove that if r is irrational, then √(r) is also irrational.
• Solution: Recall that, unlike irrational numbers, rational numbers are equal to a ratio of integers. We would need to show that if r is not a ratio of integers, then √(r) is also not a ratio of integers. It is simpler to prove the contrapositive: If √(r) is rational, then r is also rational.
• Proof: We prove the contrapositive: if √(r) is rational, then r is also rational.

Assume that √(r) is rational. Then there exist integers a and b such that:

√(r) = a / b

Squaring both sides gives:

r = a² / b²

Since a² and b² are both integers, r is also rational.

Proving an "If and Only If" Statement

Many mathematical theorems assert that two statements are logically equivalent--that is, one holds if and only if the other does.